AtCoder Beginner Contest 366 A-F 题解

A - Election 2

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, A , B ; cin >> N >> A >> B;
    int A_ = N - (A + B) + A;
    if (A_ < B) {
        cout << "Yes" << endl;
        return 0;
    }
    int B_ = N - (A + B) + B;
    if (B_ < A) {
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
    return 0;
}

B - Vertical Writing

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N; cin >> N;
    vector<string> S(N);
    int M = -1;
    for (int i = 0; i < N; i++) {
        cin >> S[i];
        M = max(M, (int)S[i].size());
    }
    vector<vector<char>> A(N, vector<char>(M, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < S[i].size(); j++) {
            A[i][j] = S[i][j];
        }
        for (int j = S[i].size(); j < M; j++) {
            A[i][j] = '*';
        }
    }
    for (int j = 0; j < M; j++) {
        for (int i = 0; i < N; i++) {
            if (A[i][j] == '*') A[i][j] = ' ';
            else break;
        }
    }
    for (int j = 0; j < M; j++) {
        for (int i = N - 1; i >= 0; i--) {
            cout << A[i][j];
        }
        cout << endl;
    }
    return 0;
}

C - Balls and Bag Query

Solution

使用 p 数组记录一个数出现了几次，用 $c n t$ 维护答案

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int main() {
    int Q; cin >> Q;
    vector<int> p(maxn, 0);
    int cnt = 0;
    while (Q--) {
        int op; cin >> op;
        if (op == 1) {
            int x; cin >> x;
            if (p[x]++ == 0) cnt += 1;
        }
        else if (op == 2) {
            int x; cin >> x;
            if (--p[x] == 0) cnt -= 1;
        }
        else {
            cout << cnt << endl;
        }
    }
}

D - Cuboid Sum Query

Solution

三维容斥

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    ios::sync_with_stdio(0);
    int n; cin >> n;
    vector<vector<vector<int>>> a(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++) {
                cin >> a[i][j][k];
            }
    vector<vector<vector<int>>> s(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++) {
                s[i][j][k] = s[i - 1][j][k] + s[i][j - 1][k] + s[i][j][k - 1] - s[i - 1][j - 1][k] - s[i - 1][j][k - 1] - s[i][j - 1][k - 1] + s[i - 1][j - 1][k - 1] + a[i][j][k];
            }
    int Q; cin >> Q;
    while (Q--) {
        int x1, y1, z1, x2, y2, z2; cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
        cout << s[x2][y2][z2] - s[x1 - 1][y2][z2] - s[x2][y1 - 1][z2] - s[x2][y2][z1 - 1] + s[x1 - 1][y1 - 1][z2] + s[x1 - 1][y2][z1 - 1] + s[x2][y1 - 1][z1 - 1] - s[x1 - 1][y1 - 1][z1 - 1] << endl;
    }
    return 0;
}

E - Manhattan Multifocal Ellipse

Question

给定 $N$ 个点 $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{N}, y_{N})$ 在二维平面上，以及非负整数 $D$ 。

找出满足 $\sum_{i = 1}^{N} (| x - x_{i} | + | y - y_{i} |) \leq D$ 的整数对 $(x, y)$ 的数量。

Solution

先把 $x, y$ 分开，其实可以独立的来看这个问题

设 $f (x) = \sum_{i = 1}^{N} | x - x_{i} |, g (y) = \sum_{i = 1}^{N} | y - y_{i} |$ ，那么答案就是满足 $f (x) + g (y) \leq D$ 的 $(x, y)$ 数对的数量

首先，我们发现值域其实不大，我们需要对序列中的每个 $x \in {- (M + D), M + D}$ ，都求出其 $f (x)$ ，我们可以用递推来计算，假设我们已知 $f (x - 1)$ ，并且知道比 $x$ 小的 $x_{i}$ 有 $k$ 个，那么有 $k$ 个的距离需要增加 $1$ ，有 $N - k$ 个的距离需要减少 $1$ ，所以， $f (x) = f (x - 1) + k - (N - k) = f (x - 1) + 2 \times k - N$

同理，我们也能算出 $g (y)$

算出了 $f (x), g (y)$ 由于是 $(x, y)$ 是独立的，所以可以把 $f (x), g (y)$ 都从小到大排序，然后用一种所谓 "尺取法" 的东西（Atcoder题解叫这个，我感觉就是指针）

我们需要满足 $f (x) + g (y) \leq D$ ，我们把 $x$ 从大到小枚举，然后令指针 $j = 0$ 指向 $g (y)$ 最小的节点，找到满足 $f (x) + g (y) \leq D$ 最大的 $y_{j}^{'}$ ，那么对于这个 $x_{i}$ ，就有 $j$ 个 $y$ 满足条件

Code

N, D = map(int, input().split())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
M = 2 * 10 ** 6


def calc(x):
    xsum = [0] * (2 * M + 1)
    x.sort()
    i = 0
    xsum[-M] = sum(x) + N * M
    for j in range(-M + 1, M + 1):
        while i < N and x[i] < j:
            i += 1
        xsum[j] = xsum[j - 1] + 2 * i - N
    return xsum

xsum = calc(x)
ysum = calc(y)
ans = 0
xsum.sort()
ysum.sort()
j = 0
for i in range(2 * M + 1)[::-1]:
    while j < 2 * M + 1 and xsum[i] + ysum[j] <= D:
        j += 1
    ans += j
print(ans)

F - Maximum Composition

Question

给定 $N$ 条线性函数 $f_{1}, f_{2}, \dots, f_{N}$ ，其中 $f_{i} (x) = A_{i} x + B_{i}$ 。

对于一个由 $K$ 个 不同的 整数 $p = (p_{1}, p_{2}, \dots, p_{K})$ 组成的序列，计算 $f_{p_{1}} (f_{p_{2}} (\dots f_{p_{K}} (1) \dots))$ 的最大可能值，其中 $p_{i}$ 的取值范围为 $1$ 到 $N$ 。

Solution

先考虑 $f_{i} (f_{j} (x)) > f_{j} (f_{i} (x))$ 的等价条件

\begin{aligned} f_{i} (f_{j} (x)) > f_{j} (f_{i} (x)) \\ \Leftrightarrow & A_{i} (A_{j} x + B_{j}) + B_{i} > A_{j} (A_{i} x + B_{i}) + B_{j} \\ \Leftrightarrow & A_{i} A_{j} x + A_{i} B_{j} + B_{i} > A_{i} A_{j} x + A_{j} B_{i} + B_{j} \\ \Leftrightarrow & A_{i} B_{j} - B_{j} > A_{j} B_{i} - B_{i} \\ \Leftrightarrow & (A_{i} - 1) B_{j} > (A_{j} - 1) B_{i} \\ \Leftrightarrow & \frac{(A_{i} - 1)}{B_{i}} > \frac{(A_{j} - 1)}{B_{j}} \end{aligned}

所以，我们按照 $\frac{(A_{i} - 1)}{B_{i}} > \frac{(A_{j} - 1)}{B_{j}}$ 的标准，把 $(A, B)$ 排序

现在我们排完序后有 $N$ 个 $(A, B)$ 我们需要从中选 $K$ 个，这个就是一个很朴素的 DP 问题了

定义 $f [i] [j]$ 对于前 $i$ ，已经选了 $j$ 个的最优解，那么转移方程就是

f [i] [j] = max f [i - 1] [j], f [i - 1] [j - 1] \times A_{j} + B_{j}

答案就是 $f [N] [K]$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    vector<int> ord(n);
    for (int i = 0; i < n; i++) ord[i] = i;
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return b[i] * (a[j] - 1) > b[j] * (a[i] - 1);
    });
    vector<ll> dp(k + 1, -INF);
    dp[0] = 1;
    for (auto i : ord) {
        auto ndp = dp;
        for (int j = 0; j < k; j++) {
            if (dp[j] != -INF) {
                ndp[j + 1] = max(ndp[j + 1], dp[j] * a[i] + b[i]);
            }
        }
        dp = ndp;
    }
    cout << dp[k] << endl;
    return 0;
}